class Solution {
public:
    vector<int> row, col; vector<pair<int,int>> pos;
    vector<string> temp;
    vector<vector<string>> ans;
    bool isvalid(int i, int j){
        for(auto& it:row){
            if(it == i) return false;
        }
        for(auto& it:col){
            if(it == j) return false;
        }
        for(auto& it:pos){
            if(abs(i-it.first) == abs(j-it.second)) return false;
        }
        return true;
    }
    void dfs(int k, int n){
        if(k == n){
            ans.emplace_back(temp);
            return;
        }
        for(int j=0; j<n; ++j){
            if(!isvalid(k, j)) continue;
            row.push_back(k);
            col.push_back(j);
            pos.push_back({k, j});
            temp[k][j] = 'Q';
            dfs(k+1, n);
            temp[k][j] = '.';
            pos.pop_back();
            col.pop_back();
            row.pop_back();
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        string str;
        for(int i=0; i<n; ++i) str+='.';
        for(int i=0; i<n; ++i)  temp.emplace_back(str);
        dfs(0, n);
        return ans;
    }
};